// Copyright 2024 Tvux
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package _380

import "math/rand"

// 使用 map 来实现 set 是可以的，但是本题还有一个关键是要相同的概率取出元素
// 而 map 取出元素的概率是随机的，不是相同概率。
//type RandomizedSet struct {
//	s map[int]struct{}
//}
//
//func Constructor() RandomizedSet {
//	return RandomizedSet{make(map[int]struct{})}
//}
//
//func (this *RandomizedSet) Insert(val int) bool {
//	if _, ok := this.s[val]; !ok {
//		this.s[val] = struct{}{}
//		return true
//	}
//	return false
//}
//
//func (this *RandomizedSet) Remove(val int) bool {
//	if _, ok := this.s[val]; ok {
//		delete(this.s, val)
//		return true
//	}
//	return false
//}
//
//func (this *RandomizedSet) GetRandom() int {
//	for k, _ := range this.s {
//		return k
//	}
//	return -1
//}

// RandomizedSet
// 切片+哈希表
// 切片：记录当前set中有哪些元素
// 哈希表：key-元素，val-在切片中的索引
type RandomizedSet struct {
	nums      []int
	hashTable map[int]int
}

func Constructor() RandomizedSet {
	return RandomizedSet{
		nums:      []int{},
		hashTable: map[int]int{},
	}
}

func (this *RandomizedSet) Insert(val int) bool {
	if _, ok := this.hashTable[val]; ok {
		return false
	}
	this.hashTable[val] = len(this.nums)
	this.nums = append(this.nums, val)
	return true
}

func (this *RandomizedSet) Remove(val int) bool {
	if _, ok := this.hashTable[val]; !ok {
		return false
	}
	index := this.hashTable[val]
	lastIndex := len(this.nums) - 1
	this.nums[index] = this.nums[lastIndex]  // 直接将最后一个元素的值覆盖到val的下标上
	this.hashTable[this.nums[index]] = index // 更新覆盖过来的最后一个元素的下标
	this.nums = this.nums[:lastIndex]        // 删除最后一个元素
	delete(this.hashTable, val)              // 别忘了还要删除哈希表中的val
	return true
}

func (this *RandomizedSet) GetRandom() int {
	return this.nums[rand.Intn(len(this.nums))]
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */
